package com.demo.java.OD251_300.OD267;

import java.util.Scanner;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【查找充电设备组合】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146065536
 */
public class OdMain {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(); // 充电设备的数量
        int[] p = new int[n]; // 存储每个设备的输出功率

        // 读取每个充电设备的输出功率
        for (int i = 0; i < n; i++) {
            p[i] = scanner.nextInt();
        }

        int pMax = scanner.nextInt(); // 最大功率限制

        // 输出最大功率组合
        System.out.println(solveMethod(n, p, pMax));
    }

    // 动态规划求解最大功率组合
    public static int solveMethod(int n, int[] p, int pMax) {
        // dp[j] 表示功率总和为 j 时，能够得到的最大功率
        int[] dp = new int[pMax + 1];

        // 遍历所有设备
        for (int i = 0; i < n; i++) {
            // 从后往前遍历，确保每个设备只选择一次
            for (int j = pMax; j >= p[i]; j--) {
                // 更新当前功率总和下的最大功率
                dp[j] = Math.max(dp[j], dp[j - p[i]] + p[i]);
            }
        }

        // 返回最大功率组合
        return dp[pMax];
    }
}